package 剑指offer;

public class _45把数组排成最小的数 {
	public static void main(String[] args) {
		String A = "1234";
		String B = "123";
		System.out.println(B.compareTo(A));//大于返回1 等于返回0  小于返回-1
	}
	/**
	 * 
	 *@time 2021年3月19日上午8:46:56
	 * 
	 *@param nums
	 *@return String
	 *
	 *@see
	 *此题求拼接起来的最小数字，本质上是一个排序问题。
	 *设数组 nums nums 中任意两数字的字符串为 xx 和 yy 
	 *，则规定 排序判断规则 为：
	 *若拼接字符串 x + y > y + x  ，则 x “大于” y ；
	 *反之，若 x + y < y + x ，则 x “小于” y ；
	 *需修改快速排序函数中的排序判断规则。字符串大小（字典序）对比的实现方法
	 *Java 中使用函数 A.compareTo(B):都是为数字类型 ，若A的数字大于B返回1 等于返回0  小于返回-1；
	 *
	 */
    public String minNumber(int[] nums) {
    	String []strs = new String[nums.length];
    	for (int i = 0; i < nums.length; i++) {
			strs[i] = ""+nums[i];
		}
    	quickSort(strs, 0, nums.length);
    	StringBuilder res =new StringBuilder();
    	for (String string : strs) {
			res.append(string);
		}
		return res.toString();
    }
    void quickSort(String[] strs, int l, int r) {
    	if(l >= r) return;
    	int i = l,j = r;//选择最左边的为基准
    	
    	String  temp = strs[i];
    	while(i<j) {
    		while(i<j&&(strs[j]+strs[l]).compareTo(strs[l]+strs[j]) >= 0) j--;
    		while(i<j&&(strs[l]+strs[i]).compareTo(strs[i]+strs[l]) >= 0) i++;
    		temp = strs[i];
    		strs[i] = strs[j];
    		strs[j] = temp;
    	}
    	strs[i] = strs[l];
    	strs[i] = temp;
    	quickSort(strs, l, i-1);
    	quickSort(strs, i+1, r);
    }

}
